package mryao.tree;

/**
 * 二叉查询树
 */
public class BSTTree extends binaryTree{

    public BSTTree(){
        super.setRoot(new treeNode<Integer>());
    }

    public BSTTree(int value){
        super.setRoot(new treeNode<Integer>(value));
    }

    public void insert(int value){
        if(super.getRoot() == null){
            super.setRoot(new treeNode<Integer>(value));
        }else{
            nodeInsert(super.getRoot(),value);
        }
    }

    public void nodeInsert(treeNode<Integer> current, int value){
        treeNode nodeToInsert = new treeNode(value);
        if(value < current.getData()){
            treeNode left = current.getLeft();
            if(left == null){
                current.setLeft(nodeToInsert);
            }else{
                nodeInsert(left,value);
            }
        }
        if(value > current.getData()){
            treeNode right = current.getRight();
            if(right == null){
                current.setRight(nodeToInsert);
            }else{
                nodeInsert(right,value);
            }
        }
        if(value == current.getData()){
            System.out.println("已经存在");
        }
    }

    public treeNode find(int value){
        if(super.root == null){
            System.out.println("不存在");
        }
        treeNode<Integer> curr = super.root;
        while (curr != null){
            if(value > curr.getData()){
                curr = curr.getRight();
            }else if(value < curr.getData()){
                curr = curr.getLeft();
            }else if(value == curr.getData()){
                return curr;
            }
        }
        System.out.println(value + " 不存在");
        return null;
    }

    public void delete(int value){
        treeNode<Integer> parentNode = null;             //待删除结点的父结点
        treeNode<Integer> toDeleteNode = null;           //待删除结点
        String direction = "";                           //待删除结点是左树 还是 右树
        treeNode<Integer> currNode = super.getRoot();    //当前结点 从根开始
        if(currNode == null){
            //根为空 直接退出
            return ;
        }
        //先找到待删除的结点 和 待删除结点的父节点
        while(currNode !=null){
            if(value > currNode.getData()){
                parentNode = currNode;
                direction = "right";
                currNode = currNode.getRight();
            }else if(value < currNode.getData()){
                parentNode = currNode;
                direction = "left";
                currNode = currNode.getLeft();
            }else if(value == currNode.getData()){
                toDeleteNode = currNode;
                if(null == parentNode) {
                    //父节点为空 说明 要删除的是根
                    System.out.println("\ntoDeleteNode：   root" );
                    break;
                }else {
                    System.out.println("\nparentNode：     " + parentNode);
                    System.out.println("\ndirection：      " + direction);
                    System.out.println("\ntoDeleteNode：   " + toDeleteNode);
                    break ;
                }
            }
        }
        //找到要删除的结点后 分情况删除
        //待删除结点没有子节点
        if(toDeleteNode.getRight() == null && toDeleteNode.getLeft() == null){
            if(parentNode == null){
                //没有父节点 就是直接删除根节点 也就是 删除树
                super.setRoot(null);
            }else{
                //有父结点 直接删除它 并且把它和父结点的关系清楚
                toDeleteNode = null;
                if(direction == "right"){
                    parentNode.setRight(null);
                }else{
                    parentNode.setLeft(null);
                }
            }
            //退出
            return ;
        }
        //删除的结点只有左子树
        if(toDeleteNode.hasLeft()&& !toDeleteNode.hasRight()){
            if(parentNode == null){
                //为根的时候 root 直接等于左子树
                super.setRoot(toDeleteNode.getLeft());
                toDeleteNode = null;
            }else{
                //不为根
                if(direction == "right"){
                    parentNode.setRight(toDeleteNode.getLeft());
                }else{
                    parentNode.setLeft(toDeleteNode.getLeft());
                }
                toDeleteNode = null;
            }
            return ;
        }
        //只有右树
        if(!toDeleteNode.hasLeft()&& toDeleteNode.hasRight()){
            if(parentNode == null){
                //为根的时候 root 直接等于右子树
                super.setRoot(toDeleteNode.getRight());
                toDeleteNode = null;
            }else{
                //不为根
                if(direction == "right"){
                    parentNode.setRight(toDeleteNode.getRight());
                }else{
                    parentNode.setLeft(toDeleteNode.getRight());
                }
                toDeleteNode = null;
            }
            return ;
        }
        //左右都有子树
        if(toDeleteNode.hasLeft() && toDeleteNode.hasRight()){
            // 寻找前驱 (左边最大的那个结点) 删掉  这个最大的结点 必定是一个 只有左结点 或者 没有子结点 的结点
            int leftMax = getLeftMaxNode(currNode).getData();
            delete(leftMax);
            //删掉前趋结点后 把 前趋结点的值给要删掉的结点
            toDeleteNode.setData(leftMax);
            //另一种 用后继
//            int rightMax = getRightMinNode(currNode).data;
//            delete(rightMax);
//            toDeleteNode.data = rightMax;
        }
    }

    //寻找前趋结点
    public treeNode<Integer> getLeftMaxNode(treeNode<Integer> currNode){
        if(currNode == null || !currNode.hasLeft()){
            return null;
        }
        currNode = currNode.getLeft();
        while (currNode.hasRight()){
            currNode = currNode.getRight();
        }
        return currNode;
    }

    public treeNode<Integer> getRightMinNode(treeNode<Integer> currNode){
        if(currNode == null || !currNode.hasRight()){
            return null;
        }
        currNode = currNode.getRight();
        while (currNode.hasLeft()){
            currNode = currNode.getLeft();
        }
        return currNode;
    }
}
